home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ASME's Mechanical Engine…ing Toolkit 1997 December
/
ASME's Mechanical Engineering Toolkit 1997 December.iso
/
ai
/
pdproprg.lzh
/
SORT.PRO
< prev
next >
Wrap
Text File
|
1985-12-31
|
2KB
|
87 lines
/* Sorting Lists */
/*
The order predicate determines how you would like the list to be ordered:
*/
order( A, B ) :- A > B.
/* The bubble sort. Invoke as ?-busort( [1,2,3], Sortlist ).
The answer is instantiated as the sorted list. */
busort( L, S ) :-
append( X, [A, B|Y], L ),
order( A, B ),
append( X, [B,A|Y], M ),
busort( M, S ).
busort( L, L ).
/* Used by most sorting algorithms. */
append( [], L, L ).
append( [H|T], L, [H|V] ) :- append( T, L, V ).
/* The quick sort. */
quisort( [H|T], S ) :-
split( H, T, A, B ),
quisort( A, A1 ),
quisort( B, B1 ),
append( A1, [H|B1], S ).
/* This important clause was left out by Clocksin and Mellish: */
quisort( [], [] ).
/* List splitting predicates used by both quick sort algorithms: */
split( H, [A|X], [A|Y], Z ) :- order( A, H ), split( H, X, Y, Z ).
split( H, [A|X], Y, [A|Z] ) :- order( H, A ), split( H, X, Y, Z ).
split( _, [], [], [] ).
/*
A compact form of the quick sort.
Invoke as: ?-quisort( List, Sortlist, [] ).
*/
quisortx( [H|T], S, X ) :-
split( H, T, A, B ),
quisortx( A, S, [H|Y] ),
quisortx( B, Y, X ).
quisortx( [], X, X ).
/*
The insertion sort:
Invoke as ?-insort( List, Sortlist ).
*/
insort( [], [] ).
insort( [X|L], M ) :- insort( L, N ), insortx( X, N, M ).
insortx( X, [A|L], [A|M] ) :- order( A, X ), !, insortx( X, L, M ).
insortx( X, L, [X|L] ).
insort( [], [], _ ).
insort( [X|L], M, O ) :- insort( L, N, O ), insortx( X, N, M, O ).
/*
This form of the insertion sort needs no sort parameter.
O is instantiated to a predicate or operator which orders the elements.
Invoke as: insort( List, Sortlist, <order> ).
For instance, ?-insort( List, Sortlist, < ).
*/
insortb( [], [], _).
insortb( [X|L], M, O ) :- insortb( L, N, O ), insortxb( X, N, M, O ).
insortxb( X, [A|L], [A|M], O ) :-
P =.. [ O, A, X ],
P,
!,
insortxb( X, L, M, O ).
insortxb( X, L, [X|L], O ).